#pragma once
#include <array>
#include <utility>

template<typename T, size_t N>
void MergeGrow(std::array<T, N>& arr, int mfirst, int half, int msecond)
{
	if (msecond - mfirst == 0) return;

	int first = mfirst - 1, second = msecond - 1;//������������� ������� �������� � ������ ��������� � �������

	if (second - first == 1) {
		if (arr[first] > arr[second]) { std::swap(arr[first], arr[second]); }
		return;
	}

	int i = 0;
	std::array<T, N> tmp{};
	int start_half = half;

	while (i <= msecond - mfirst)
	{		
		if (first >= start_half || half <= second && arr[first] >= arr[half])
		{
			tmp[i] = arr[half];
			half++;
		}
		else {			
				tmp[i] = arr[first];
				first++;

		}	
		i++;
	}	
	
		int tmpi = 0;
		for (size_t arri = mfirst - 1; arri < msecond; arri++) {
			arr[arri] = tmp[tmpi];
			tmpi++;
		}
}

//���������� ������������ � ���������� ���������
template<typename T, size_t N>
void Sort(std::array<T, N>& arr, int first, int second)
{
	if (first < second)
	{
		int half = (first + second) / 2;
		Sort(arr, first, half);
		Sort(arr, half + 1, second);
		MergeGrow(arr, first, half, second);//Ascending
	}
}

